﻿#if false
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hash{}; // key: num, value: cnt
        for (int num : nums) ++hash[num];

        priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<>> heap;
        for (auto&& [cnt, num] : hash) {
            if (heap.size() != k) heap.emplace(make_pair(cnt, num));
            else {
                if (cnt > heap.top().first) {
                    heap.pop();
                    heap.emplace(make_pair(cnt, num));
                }
            }
        }

        vector<int> ans;
        while (!heap.empty()) {
            ans.emplace_back(heap.top().second);
            heap.pop();
        }

        return ans;
    }
};

int main() {
    vector<int> nums{ 1,1,1,2,2,3,2,3,3,2,1,3 };
    Solution().topKFrequent(nums, 3);
    return 0;
}

#endif

#if false
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        // 我们借助nums来作栈, 栈顶元素 | right_or == 窗口or值
        int ans = INT_MAX, left = 0, bottom = -1, right_or = 0; // left: 滑动窗口左端点，bottom: 栈底， right_or: [bottom + 1, right]的or结果

        int n = nums.size();
        for (int right = 0; right < n; ++right) {
            right_or |= nums[right]; // 入窗口

            // 出窗口, 因为or的结果是越来越大的，所以当窗口的or值超过k了，就应出窗口了，不然窗口的值越来越大，就得不到答案了
            while (left <= right && ((nums[left] | right_or) > k)) {
                ans = std::min(ans, (nums[left] | right_or) - k); // 更新结果，最小值滑窗

                // 栈已经被出完了（栈底马上就会被移除，只是现在还没移而已）
                if (left >= bottom) {
                    // 重新构建一个栈，因为left就是栈底的位置，且马上就要被出掉了，所以不需要计算
                    for (int i = right - 1; i > left; --i) {
                        nums[i] |= nums[i + 1];
                    }

                    // 更新栈底
                    // 为什么栈底是right呢，因为一个元素也可以做子数组，
                    // 又因为nums[right] | nums[right] == nums[right]，计算它毫无意义，所以没有在循环中计算而已
                    // 但本质上它也是栈的一部分，且作为栈底存在
                    bottom = right;
                    right_or = 0;

                    ++left;
                }

                // if (left <= right)
                ans = std::min(ans, k - (nums[left] | right_or)); // 更新结果，最大值滑窗
            }
        }

        return ans;
    }
};

int main() {
    vector<int> vec{ 1,2,4,5 };
    Solution().minimumDifference(vec, 3);
    return 0;
}

#endif

#if false
#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        vector<string> path;

        // i 为起始位置 k为现在被分成了几段
        int n = s.size();
        auto dfs = [&](auto&& dfs, int i) {
            if (n == i && path.size() == 4) {
                string ip{};
                for (const string& str : path) {
                    ip += str;
                    ip += '.';
                }

                ip.pop_back();
                ret.emplace_back(std::move(ip));
                return;
            }

            for (int j = i; j < n; ++j) {
                int len = j - i + 1;
                string str = s.substr(i, len);
                if (!valid(str)) continue;
                path.emplace_back(std::move(str));
                dfs(dfs, j + len);
                path.pop_back();
            }
        };

        dfs(dfs, 0);
        return ret;
    }

private:
    bool valid(const string& str) {
        // 包含前导0
        if (str.size() > 1 && '0' == str[0]) return false;

        long long num = stoll(str);
        return 0 <= num && num <= 255;
    }
};

int main() {
    auto ret = Solution().restoreIpAddresses("101023");
    for (const auto& str : ret) cout << str << " ";
    cout << endl;
    return 0;
}

#endif

#if true
#include <vector>
#include <ranges>
#include <algorithm>
using namespace std;
class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        ranges::sort(rewardValues);
        int m = rewardValues.size(), n = rewardValues.back() * 2; // 可获得的最大总奖励 <= 2 * max_val - 1

        vector<vector<unsigned char>> dp(m + 1, vector<unsigned char>(n)); // 在前i个数中 能不能获得价值为j的总奖励
        dp[0][0] = true;

        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[i][j] = dp[i - 1][j]; // 不选该位置
                if (j >= rewardValues[i - 1]) dp[i][j] |= dp[i - 1][j - rewardValues[i - 1]]; // 选该位置
            }
        }

        int j = n - 1;
        for (; j >= 1; --j) {
            if (dp[m][j]) break;
        }

        return j;
    }
};

int main() {
    vector<int> vec{ 1,1,3,3 };
    Solution().maxTotalReward(vec);

    return 0;
}

#endif